// 二叉树和二叉搜索树
// 二叉树中的节点最多只能有两个子节点：
// 一个是左侧子节点，另一个是右侧子节点
// 
// 二叉搜索树(BST)是二叉树的一种，
// 但是它只允许你在左侧节点存储(比父节点)小的值，
// 在右侧节点存储(比父节点)大(或者等于)的值

function BinarySearchTree(){

	var Node = function(key){
		this.key = key;    // 在树中，称节点本身为键
		this.left = null;
		this.right = null;
	}

	var root = null;
	this.getRoot = function(){return root;}

	var insertNode = function(node, newNode){
		if(newNode.key < node.key){
			if(node.left === null){
				node.left = newNode;
			} else {
				insertNode(node.left, newNode);
			}
		} else {
			if(node.right === null){
				node.right = newNode;
			} else {
				insertNode(node.right, newNode);
			}
		}
	}

	var inOrderTraverseNode = function(node, callback){
		if(node !== null){
			inOrderTraverseNode(node.left, callback);
			callback(node.key);
			inOrderTraverseNode(node.right, callback);
		}
	}

	var preOrderTraverseNode = function(node, callback){
		if(node !== null){
			callback(node.key);
			preOrderTraverseNode(node.left, callback);
			preOrderTraverseNode(node.right, callback);
		}
	}

	var postOrderTraverseNode = function(node, callback){
		if(node !== null){
			postOrderTraverseNode(node.left, callback);
			postOrderTraverseNode(node.right, callback);
			callback(node.key);
		}
	}

	var minNode = function(node){
		if(node){
			while(node.left !== null){
				node = node.left;
			}
			return node.key;
		}
		return null;
	}

	var maxNode = function(node){
		if(node){
			while(node.right !== null){
				node = node.right;
			}
			return node.key;
		}
		return null;
	}

	var searchNode = function(node, key){
		if(node === null){
			return false;
		}

		if(key < node.key){
			return searchNode(node.left, key);
		} else if(key > node.key) {
			return searchNode(node.right, key);
		} else {
			return true;
		}
	}

	var removeNode = function(node, key){
		if(node === null){
			return null;
		}
		if(key < node.key){
			node.left = removeNode(node.left, key);
			return node;
		} else if(key > node.key){
			node.right = removeNode(node.right, key);
			return node;
		} else{
			// 第一种情况——一个叶节点
			if(node.left === null && node.right === null){
				node = null;
				return node;
			}

			// 第二种情况——一个只有一个子节点的节点
			if(node.left === null){
				node = node.right;
				return node;
			} else if(node.right === null){
				node = node.left;
				return node;
			}

			// 第三种情况——一个有两个子节点的节点
			var aux = findMinNode(node.right); // 右侧最小的节点
			node.key = aux.key; // 将移除掉的节点更新为右侧最小的节点
			node.right = removeNode(node.right, aux.key); // 再递归移除右侧的最小节点
			return node;
		}
	}

	var findMinNode = function(node){
		if(node === null){
			return null;
		} else {
			while(node.left){
				node = node.left;
			}
			return node;
		}
	}

	this.insert = function(key){
		var node = new Node(key);
		if(root === null){
			root = node;
		} else {
			insertNode(root, node);
		}
	}

	this.search = function(key){}

	/**
	 * 通过中序遍历方式遍历所有节点
	 * 一种以上行顺序访问BST所有节点的遍历方式，
	 * 也就是以从最小到最大的顺序访问所有节点
	 * @return {[type]} [description]
	 */
	this.inOrderTraverse = function(callback){
		inOrderTraverseNode(root, callback);
	}

	/**
	 * 通过先序遍历方式遍历所有节点
	 * 以优先于后代节点的顺序访问每个节点
	 * 先序遍历的一种应用是打印一个结构化的文档
	 * @return {[type]} [description]
	 */
	this.preOrderTraverse = function(callback){
		preOrderTraverseNode(root, callback);
	}

	/**
	 * 通过后序遍历方式遍历所有节点
	 * 先访问节点的后代节点，再访问节点本身
	 * 后序遍历的一种应用是计算一个目录和它的子目录中所有文件所占空间的大小
	 * @return {[type]} [description]
	 */
	this.postOrderTraverse = function(callback){
		postOrderTraverseNode(root, callback);
	}

	this.min = function(){
		return minNode(root);
	}

	this.max = function(){
		return maxNode(root);
	}

	this.search = function(key){
		return searchNode(root, key);
	}

	this.remove = function(key){
		root = removeNode(root, key);
	}
}